package thired.class03_structure;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Class01_DoubleEndsQueueToStackAndQueue {
        public static class Node<T> {
                private T value;
                private Node<T> last;
                private Node<T> next;

                public Node(T val) {
                        this.value = val;
                }

        }
        public static class DoubleEndList<T>{
                private Node<T> head;
                private Node<T> tail;

                public void addFromHead(T value){
                        Node<T> cur = new Node<T>(value);
                        if (head == null) {
                                head = cur;
                                tail = cur;
                        } else {
                                cur.next = head;
                                head.last = cur;
                                head = cur;
                        }
                }

                public void addFromTail(T value){
                        Node<T> cur = new Node<T>(value);
                        if (head == null) {
                                head = cur;
                                tail = cur;
                        } else {
                                cur.last = tail;
                                tail.next = cur;
                                tail = cur;
                        }
                }
                public T popFromHead() {
                        if (head == null) {
                                return null;
                        }
                        Node<T> cur = head;
                        if (head == tail) {
                                head = null;
                                tail = null;
                        } else {
                                head = head.next;
                                cur.next = null;
                                head.last = null;
                        }
                        return cur.value;
                }

                public T popFromBottom() {
                        if (head == null) {
                                return null;
                        }
                        Node<T> cur = tail;
                        if (head == tail) {
                                head = null;
                                tail = null;
                        } else {
                                tail = tail.last;
                                tail.next = null;
                                cur.last = null;
                        }
                        return cur.value;
                }

                public boolean isEmpty() {
                        return head == null;
                }
        }

        public static class MyStack<T> {
                private DoubleEndList<T> queue;

                public MyStack() {
                        queue = new DoubleEndList<>();
                }

                public void push(T value) {
                        queue.addFromHead(value);
                }

                public T pop() {
                        return queue.popFromHead();
                }

                public boolean isEmpty() {
                        return queue.isEmpty();
                }

        }

        public static class MyQueue<T> {
                private DoubleEndList<T> queue;

                public MyQueue() {
                        queue = new DoubleEndList<T>();
                }

                public void push(T value) {
                        queue.addFromHead(value);
                }

                public T poll() {
                        return queue.popFromBottom();
                }

                public boolean isEmpty() {
                        return queue.isEmpty();
                }

        }

        public static boolean isEqual(Integer o1, Integer o2) {
                if (o1 == null && o2 != null) {
                        return false;
                }
                if (o1 != null && o2 == null) {
                        return false;
                }
                if (o1 == null && o2 == null) {
                        return true;
                }
                return o1.equals(o2);
        }

        public static void main(String[] args) {
                int oneTestDataNum = 100;
                int value = 10000;
                int testTimes = 100000;
                for (int i = 0; i < testTimes; i++) {
                        MyStack<Integer> myStack = new MyStack<>();
                        MyQueue<Integer> myQueue = new MyQueue<>();
                        Stack<Integer> stack = new Stack<>();
                        Queue<Integer> queue = new LinkedList<>();
                        for (int j = 0; j < oneTestDataNum; j++) {
                                int nums = (int) (Math.random() * value);
                                if (stack.isEmpty()) {
                                        myStack.push(nums);
                                        stack.push(nums);
                                } else {
                                        if (Math.random() < 0.5) {
                                                myStack.push(nums);
                                                stack.push(nums);
                                        } else {
                                                if (!isEqual(myStack.pop(), stack.pop())) {
                                                        System.out.println("oops!");
                                                }
                                        }
                                }
                                int numq = (int) (Math.random() * value);
                                if (stack.isEmpty()) {
                                        myQueue.push(numq);
                                        queue.offer(numq);
                                } else {
                                        if (Math.random() < 0.5) {
                                                myQueue.push(numq);
                                                queue.offer(numq);
                                        } else {
                                                if (!isEqual(myQueue.poll(), queue.poll())) {
                                                        System.out.println("oops!");
                                                }
                                        }
                                }
                        }
                }
                System.out.println("finish!");
        }


}
